package com.aqie.easy.binaryTree;

import com.aqie.easy.structure.TreeNode;

import java.util.*;

/**
 * @Function: 107. 二叉树的层次遍历 II
 * @Author: aqie
 * @Date: 2019/6/30 19:06
 */
public class LevelOrderBottom {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            ans.add(tmp);
        }
        Collections.reverse(ans);
        return ans;
    }
}
